package top.ivansong92.example.leetcode.learning.data.struct.array.sort;

/**
 * 选择排序
 */
public class HeapSort implements ArraySort {
    @Override
    public void sort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }

        int len = array.length;
        for (int i = 0; i < len; i++) {
            for (int j = len / 2; j >= 0; j--) {
                int k = 2 * j + 1;
                if (k < len && array[k] < array[j]) {
                    swap(array, k, j);
                }

                k = 2 * j;
                if (k <len && array[k] < array[j]) {
                    swap(array, k, j);
                }
            }

        }

    }
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

}
